1186F - Vus the Cossack and a Graph - CodeForces Solution

#include <bits/stdc++.h>

#define endl '\n'

#define all(a) (a).begin(), (a).end()

#define len(a) (int) (a).size()

#define forn(i, n) for (int (i) = 0; (i) < (n); ++(i))

using namespace std;

void solve();

signed main(){

#ifdef LOCAL

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

#endif

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);



    solve();

}



#include <cstdio>



/** Interface */



inline int readChar();

template <class T = int> inline T readInt();

template <class T> inline void writeInt( T x, char end = 0 );

inline void writeChar( int x );

inline void writeWord( const char *s );



/** Read */



static const int buf_size = 40960;



inline int getChar() {

    static char buf[buf_size];

    static int len = 0, pos = 0;

    if (pos == len)

        pos = 0, len = fread(buf, 1, buf_size, stdin);

    if (pos == len)

        return -1;

    return buf[pos++];

}



inline int readChar() {

    int c = getChar();

    while (c <= 32)

        c = getChar();

    return c;

}



template <class T>

inline T readInt() {

    int s = 1, c = readChar();

    T x = 0;

    if (c == '-')

        s = -1, c = getChar();

    while ('0' <= c && c <= '9')

        x = x * 10 + c - '0', c = getChar();

    return s == 1 ? x : -x;

}



/** Write */



static int write_pos = 0;

static char write_buf[buf_size];



inline void writeChar( int x ) {

    if (write_pos == buf_size)

        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;

    write_buf[write_pos++] = x;

}



template <class T>

inline void writeInt( T x, char end ) {

    if (x < 0)

        writeChar('-'), x = -x;



    char s[24];

    int n = 0;

    while (x || !n)

        s[n++] = '0' + x % 10, x /= 10;

    while (n--)

        writeChar(s[n]);

    if (end)

        writeChar(end);

}



inline void writeWord( const char *s ) {

    while (*s)

        writeChar(*s++);

}



struct Flusher {

    ~Flusher() {

        if (write_pos)

            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;

    }

} flusher;



mt19937 rnd(2007);

void solve() {

    int n, m; n = readInt(); m = readInt();

    vector<pair<int, int>> e(m);

    forn (i, m) e[i].first = readInt(), e[i].second = readInt();

    forn (i, m) e[i].first--, e[i].second--;

    vector<int> d(n);

    for (auto i : e) d[i.first]++, d[i.second]++;

    vector<int> f = d;

    vector<pair<int, int>>  a;

    shuffle(all(e), rnd);

    for (auto i : e){

        f[i.first]--;

        f[i.second]--;

        if (f[i.first] * 2 < d[i.first] || f[i.second] * 2 < d[i.second]){

            a.push_back(i);

            f[i.first]++;

            f[i.second]++;

        }

    }

    writeInt(len(a)); writeChar('\n');

    for (auto i : a){

        writeInt(i.first + 1); writeChar(' '); writeInt(i.second + 1); writeChar('\n');

    }

}